/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:${USER}
 * Date:${YEAR}-${MONTH}-${DAY}
 * ${TIME}
 */
public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }

    /**
     * 对包含0、1、2的数组进行原地排序（荷兰国旗问题）
     * @param nums 待排序的数组，元素只能是0、1或2
     */
    public void sortColors(int[] nums) {
        int n = nums.length;
        int i = 0;          // 当前遍历的指针
        int left = -1;      // 0的右边界，初始为-1
        int right = n;      // 2的左边界，初始为n

        // 遍历数组，直到当前指针遇到2的边界
        while (i < right) {
            if (nums[i] == 0) {
                // 如果是0，交换到左边界+1的位置，并移动左边界和当前指针
                swap(nums, ++left, i++);
            } else if (nums[i] == 1) {
                // 如果是1，不做交换，继续前进
                i++;
            } else {
                // 如果是2，交换到右边界-1的位置，只移动右边界（不移动i，因为交换来的元素需要再次检查）
                swap(nums, --right, i);
            }
        }
    }


    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

}